package Hot100.Medium.GreedyAndDP.DynamicPlanning.bag_01;

public class LC416_partiSubList {
    public static void main(String[] args) {
        int num[] = {1,5,11,5};
    }

    public boolean canPartition(int[] nums){
        int n = nums.length;
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 2 == 1)
            return false;
        // 将问题转化为能不能找到几个数，让和为sum/2
        int target = sum / 2;
        // dp[i][j]的含义是，在[0,i]子区间内挑选一些数让这些数的和正好为j，j就是容量，数组中的数放进去要恰好等于这个容量
        int[][] dp = new int[n][target + 1];
        // 初始化数组,第一行放入nums[0]，然而当j < nums[0]时，dp[0][j]应该是0，因为容量j不够放下nums[0]
         for(int j = 0; j <= target; j++){
             if(j < nums[0])
                 dp[0][j] = 0;
             else
                 dp[0][j] = nums[0];
         }
         // 确定递推公式以及递推顺序，可以让选数字在外层，也就是按行从左往右写数据进入dp数组
         for(int i = 1; i < n; i++){
             for(int j = 0; j <= target; j++){
                 if(nums[i] > j){
                     dp[i][j] = dp[i - 1][j];// j小于当前数，证明放不下，则不放入nums[i]，而是依旧放上一行中的数
                 } else {
                     // j比当前数大，则nums[i]能放下，那么选不放nums[i]以及放了之后的大的那个。dp[i - 1][j - nums[i]]表示在不考虑nums[i] 的情况下（只用前 0..i-1 个数），最多能凑出的和，再加上nums[i]就是放入第i个数的情况
                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                 }
             }
         }
         return dp[n - 1][target] == target;

    }
}
